package com.practice.zuocy.base.class06;

import java.util.ArrayList;

/**
 * 快慢指针
 * （1）输入链表头节点，奇数长度返回中点，偶数长度返回上中点
 * （2）输入链表头节点，奇数长度返回中点，偶数长度返回下中点
 * （3）输入链表头节点，奇数长度返回中点前一个节点，偶数长度返回上中点前一个节点
 * （4）输入链表头节点，奇数长度返回中点前一个节点，偶数长度返回下中点前一个
 */
public class Code01_LinkedListMid {

	public static class Node {
		public int value;
		public Node next;

		public Node(int v) {
			value = v;
		}
	}

	/**
	 * （1）输入链表头节点，奇数长度返回中点，偶数长度返回上中点
	 * @param head 链表头节点
	 * @return
	 */
	// head 头
	public static Node midOrUpMidNode(Node head) {
		if (head == null || head.next == null || head.next.next == null) {
			// 情况：
			// （1）为空；
			// （2）只有一个节点；
			// （3）只有两个节点
			return head;
		}

		// 链表有3个或3个以上个节点

		// 慢指针
		Node slow = head.next;
		// 快指针
		Node fast = head.next.next;
		while (fast.next != null && fast.next.next != null) {
			// 快指针能继续往下走时，快慢指针都继续往下走：

			// 1. 慢指针一次走一步
			slow = slow.next;
			// 2. 快指针一次走两步
			fast = fast.next.next;
		}
		// 最后返回慢指针所指向的节点
		return slow;
	}

	/**
	 * （2）输入链表头节点，奇数长度返回中点，偶数长度返回下中点
	 * @param head 链表头节点
	 * @return
	 */
	public static Node midOrDownMidNode(Node head) {
		if (head == null || head.next == null) {
			return head;
		}
		Node slow = head.next;
		Node fast = head.next;
		while (fast.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}

	/**
	 * （3）输入链表头节点，奇数长度返回中点前一个节点，偶数长度返回上中点前一个节点
	 * @param head 链表头节点
	 * @return
	 */
	public static Node midOrUpMidPreNode(Node head) {
		if (head == null || head.next == null || head.next.next == null) {
			return null;
		}
		Node slow = head;
		Node fast = head.next.next;
		while (fast.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}

	/**
	 * （4）输入链表头节点，奇数长度返回中点前一个节点，偶数长度返回下中点前一个
	 * @param head 链表头节点
	 * @return
	 */
	public static Node midOrDownMidPreNode(Node head) {
		if (head == null || head.next == null) {
			return null;
		}
		if (head.next.next == null) {
			return head;
		}
		Node slow = head;
		Node fast = head.next;
		while (fast.next != null && fast.next.next != null) {
			slow = slow.next;
			fast = fast.next.next;
		}
		return slow;
	}

	// 题目（1）的暴力解
	public static Node right1(Node head) {
		if (head == null) {
			return null;
		}
		Node cur = head;
		ArrayList<Node> arr = new ArrayList<>();
		while (cur != null) {
			arr.add(cur);
			cur = cur.next;
		}
		return arr.get((arr.size() - 1) / 2);
	}

	// 题目（2）的暴力解
	public static Node right2(Node head) {
		if (head == null) {
			return null;
		}
		Node cur = head;
		ArrayList<Node> arr = new ArrayList<>();
		while (cur != null) {
			arr.add(cur);
			cur = cur.next;
		}
		return arr.get(arr.size() / 2);
	}

	// 题目（3）的暴力解
	public static Node right3(Node head) {
		if (head == null || head.next == null || head.next.next == null) {
			return null;
		}
		Node cur = head;
		ArrayList<Node> arr = new ArrayList<>();
		while (cur != null) {
			arr.add(cur);
			cur = cur.next;
		}
		return arr.get((arr.size() - 3) / 2);
	}

	// 题目（4）的暴力解
	public static Node right4(Node head) {
		if (head == null || head.next == null) {
			return null;
		}
		Node cur = head;
		ArrayList<Node> arr = new ArrayList<>();
		while (cur != null) {
			arr.add(cur);
			cur = cur.next;
		}
		return arr.get((arr.size() - 2) / 2);
	}

	public static void main(String[] args) {
		Node test = null;
		test = new Node(0);
		test.next = new Node(1);
		test.next.next = new Node(2);
		test.next.next.next = new Node(3);
		test.next.next.next.next = new Node(4);
		test.next.next.next.next.next = new Node(5);
		test.next.next.next.next.next.next = new Node(6);
		test.next.next.next.next.next.next.next = new Node(7);
		test.next.next.next.next.next.next.next.next = new Node(8);

		Node ans1 = null;
		Node ans2 = null;

		ans1 = midOrUpMidNode(test);
		ans2 = right1(test);
		System.out.println(ans1 != null ? ans1.value : "无");
		System.out.println(ans2 != null ? ans2.value : "无");

		ans1 = midOrDownMidNode(test);
		ans2 = right2(test);
		System.out.println(ans1 != null ? ans1.value : "无");
		System.out.println(ans2 != null ? ans2.value : "无");

		ans1 = midOrUpMidPreNode(test);
		ans2 = right3(test);
		System.out.println(ans1 != null ? ans1.value : "无");
		System.out.println(ans2 != null ? ans2.value : "无");

		ans1 = midOrDownMidPreNode(test);
		ans2 = right4(test);
		System.out.println(ans1 != null ? ans1.value : "无");
		System.out.println(ans2 != null ? ans2.value : "无");

	}

}
